package GreedyAlgorithm;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 一堆任务的情况下，安排最多的任务执行；
 * 贪心解法思想： 所有的任务更具结束时间排序，依此执行
 *
 * @author Liaorun
 */
public class BestArrange {

    public static class Program {
        public int start;
        public int end;

        public Program(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }


    public static class ProgramCompator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o1.end - o2.end;
        }
    }

    /**
     * 返回最多可以进行多少个会议
     *
     * @param programs  需要进行的任务
     * @param timePoint 现在的时间点
     * @return
     */
    public static int bestArrange(Program[] programs, int timePoint) {
        // 所有的任务更具结束时间排序
        Arrays.sort(programs, new ProgramCompator());

        int result = 0;
        for (Program program : programs) {

            if (timePoint <= program.start) {
                // 当前任务的开始时间大于上一个结束时间，可以安排上
                result++;
                timePoint = program.end;
            }
        }

        return result;
    }
}


